/**
 * 
 */
package edu.umd.clip.lm.util;

import java.io.Serializable;
import java.util.*;

import edu.umd.clip.lm.util.Long2DoubleMap.Entry;


/**
 * @author Denis Filimonov <den@cs.umd.edu>
 *
 */
public class Long2IntMap implements Cloneable, Serializable {
	
	private static final long serialVersionUID = 1L;
	static final int nullValue = 0;
	
	public static final class Entry implements Serializable {
		private static final long serialVersionUID = 1L;
		final long key;
		int value;
		Entry next;
		
		private Entry(long key, int value) {
			this.key = key;
			this.value = value;
			next = null;
		}

		@Override
		public String toString() {
			return String.format("%d -> %d", key, value);
		}

		public int getValue() {
			return value;
		}

		public void setValue(int value) {
			this.value = value;
		}

		public long getKey() {
			return key;
		}
	}
	
	Entry[] table;
	int size;
	float loadFactor;
	
	public Long2IntMap(int capacity, float loadFactor) {
		assert(loadFactor <= 1 && loadFactor > 0.1);
		
		int cap = 1;
		while(cap < capacity) {
			cap <<= 1;
		}
		table = new Entry[cap];
		this.loadFactor = loadFactor;
	}
	
	public Long2IntMap(int capacity) {
		this(capacity, 0.75f);
	}
	
	public Long2IntMap() {
		this(10, 0.75f);
	}
	
	final int index(long key) {
		return index(key, table.length);
	}
	
	final int index(long key, int tableLength) {
		int result = (int) (key ^ (key >>> 32));
		
        result ^= (result >>> 20) ^ (result >>> 12);
        result ^= (result >>> 7) ^ (result >>> 4);

		return result & (tableLength - 1);
	}
	
	/**
	 * @param head
	 * @param key
	 * @return the matching element or null
	 */
	private Entry find(Entry head, long key) {
		while(head != null && head.key != key) {
			head = head.next;
		}
		return head;
	}
	
	public int get(long key) {
		final int index = index(key);
		Entry entry = find(table[index], key);
		return entry == null ? nullValue : entry.value;
	}
	
	public boolean hasKey(long key) {
		final int index = index(key);
		Entry entry = find(table[index], key);
		return entry != null;
	}
	
	public int addAndGet(long key, int addition) {
		final int index = index(key);
		Entry entry = find(table[index], key);
		if (entry == null) {
			entry = new Entry(key, addition);
			entry.next = table[index];
			table[index] = entry;
			grow(++size);
		} else {
			entry.value += addition;
		}
		return entry.value;
	}
	
	public void remove(long key) {
		final int index = index(key);
		Entry head = table[index];
		Entry last = head;
		while(head != null) {
			if (head.key == key) {
				if (last == head) {
					table[index] = head.next;
				} else {
					last.next = head.next;
				}
				--size;
				return;
			}
			last = head;
			head = head.next;
		}
	}
	
	public void put(long key, int value) {
		final int index = index(key);
		Entry entry = find(table[index], key);
		if (entry == null) {
			entry = new Entry(key, value);
			entry.next = table[index];
			table[index] = entry;
			grow(++size);
		} else {
			entry.value = value;
		}
	}
	
	public final int size() {
		return size;
	}
	
	private void grow(int size) {
		if (size > table.length * loadFactor + 2) {
			resize(table.length << 1);
		}
	}
	
	private void resize(int capacity) {
		Entry[] newTable = new Entry[capacity];
		for(int i=0; i<table.length; ++i) {
			Entry head = table[i];
			while(head != null) {
				Entry next = head.next;
				
				int newIndex = index(head.key, newTable.length);
				head.next = newTable[newIndex];
				newTable[newIndex] = head;
				
				head = next;
			}
		}
		table = newTable;
	}
	
	public void clear() {
		Arrays.fill(table, null);
		size = 0;
	}
	
	public long sumValues() {
		long sum = 0;
		for(Iterator it = iterator(); it.hasNext(); ) {
			sum += it.next().getValue();
		}
		return sum;
	}
	
	public void addMap(Long2IntMap map) {
		for(Iterator it = map.iterator(); it.hasNext(); ) {
			Entry e = it.next();
			addAndGet(e.getKey(), e.getValue());
		}
	}
	
	public double computeEntropy() {
		double entropy = 0;
		long totalCount = 0;

		for(Long2IntMap.Iterator i = iterator(); i.hasNext(); ) {
			int val = i.next().getValue();
			if (val == 0) continue;
			totalCount += val;
			entropy -= val * ProbMath.log2(val);
		}
		entropy /= totalCount;
		entropy += ProbMath.log2(totalCount);
		return entropy;
	}
	
	public String toString() {
		StringBuilder sb = new StringBuilder();
		sb.append('[');
		
		Iterator iterator = iterator();
		if (iterator.hasNext()) {
			sb.append(iterator.next().toString());
			
			while(iterator.hasNext()) {
				sb.append(", ");
				sb.append(iterator.next().toString());
			}
		}
		sb.append(']');
		return sb.toString();
	}
	
	public Iterator iterator() {
		return new Iterator();
	}
	
	public final class Iterator {
		private int index;
		private Entry entry;
		private Entry nextEntry;
		
		Iterator() {
			index = 0;
			entry = null;
			nextEntry = table[index];
			if (nextEntry == null) {
				locateNext();
			}
		}
		
		private void locateNext() {
			if (nextEntry != null) {
				nextEntry = nextEntry.next;
			}
			while(nextEntry == null && index < table.length - 1) {
				nextEntry = table[++index];
			}
		}
		
		public boolean hasNext() {
			return nextEntry != null;
		}
		
		public Entry next() {
			if (nextEntry == null) {
				throw new IllegalStateException();
			}
			entry = nextEntry;
			
			locateNext();
			return entry;
		}

		public void remove() {
			if (entry != null) {
				Entry e = table[index];
				while(e != null && e.next != entry) {
					e = e.next;
				}
				if (e != null) {
					e.next = entry.next;
					--size;
				}
			}
		}
		
		public long getKey() {
			return entry.key;
		}

		public int getValue() {
			return entry.value;
		}
		
		public void setValue(int value) {
			entry.value = value;
		}
	}

	@Override
	public Object clone() {
		Long2IntMap copy = new Long2IntMap(size, loadFactor);
		for(Iterator it = iterator(); it.hasNext();) {
			Entry entry = it.next();
			copy.put(entry.getKey(), entry.getValue());
		}
		return copy;
	}
}
